#include "BinaryTree.h"

static int id = 0;

/**
 * 初始化空二叉树
 * @param tree
 */
void InitBinaryTree(BinaryTree *tree) {
    tree->root = NULL;
    tree->depth = 0;
    tree->diameter = 0;
    tree->length = 0;
}


/**
 * 构造二叉树- 外部需要事先对节点分配内存
 * @param root
 */
int CreateBinaryTree(TreeNode *root) {
    /* 根节点如果为空,就退出创建过程 */
    if (!root) {
        return 0;
    }
    /* 用户输入的节点名 */
    char inputName[NAME_SIZE];
    gets(inputName);
    /* 用户输入回车表示结束当前子树创建 */
    if (strcmp(inputName, ".") == 0) {
        return 0;
    }
    /* 创建当前节点 */
    root->data.id = ++id;
    strcpy(root->data.name, inputName);
    /* 为输入的左右节点做准备: 为左右节点指针分配内存 */
    root->left = (TreeNode *) malloc(sizeof(TreeNode));
    root->right = (TreeNode *) malloc(sizeof(TreeNode));
    /* 分别递归创建左子树和右子树 */
    printf("左节点: ");
    if (CreateBinaryTree(root->left) == 0) {
        /* 不在创建这个节点则销毁刚分配的内存 */
        free(root->left);
        root->left = NULL;
    }
    printf("右节点: ");
    if (CreateBinaryTree(root->right) == 0) {
        /* 不在创建这个节点则销毁刚分配的内存 */
        free(root->right);
        root->right = NULL;
    }
    return 1;
}

/**
 * 先序遍历: 根-左-右
 * @param node
 */
void PreOrderTraverse(TreeNode *node) {
    /* 先访问根节点,然后遍历左子树,最后遍历右子树 */
    if (node) {
        // printf("[%d,%s]-", node->data.id, node->data.name);
        printf("%-3s", node->data.name);
        /* 递归遍历左子树 */
        PreOrderTraverse(node->left);
        /* 递归遍历右子树 */
        PreOrderTraverse(node->right);

    }
}


/* 模仿用户输入的顺序 */
char *nodeNames[] = {"A", "B", "D", "#", "#", "E", "#", "#", "C", "F", "#", "#", "G", "#", "#"};
static int nodeNameIndex = 0;

/**
 * 构造二叉树- 外部需要事先对节点分配内存
 * @param root
 */
int CreateBinaryTree_Test(TreeNode *root) {
    /* 根节点如果为空,就退出创建过程 */
    if (!root) {
        return 0;
    }
    /* 用户输入的节点名 */
    char inputName[NAME_SIZE];
    strcpy(inputName, nodeNames[nodeNameIndex++]);
    /* 用户输入回车表示结束当前子树创建 */
    if (strcmp(inputName, ".") == 0) {
        return 0;
    }
    /* 创建当前节点 */
    root->data.id = ++id;
    strcpy(root->data.name, inputName);
    /* 为输入的左右节点做准备: 为左右节点指针分配内存 */
    root->left = (TreeNode *) malloc(sizeof(TreeNode));
    root->right = (TreeNode *) malloc(sizeof(TreeNode));
    /* 分别递归创建左子树和右子树 */
    if (CreateBinaryTree_Test(root->left) == 0) {
        /* 不在创建这个节点则销毁刚分配的内存 */
        free(root->left);
        root->left = NULL;
    }
    if (CreateBinaryTree_Test(root->right) == 0) {
        /* 不在创建这个节点则销毁刚分配的内存 */
        free(root->right);
        root->right = NULL;
    }
    return 1;
}


/**
 * 中序遍历: 左-根-右(左侧优先)
 * @param node
 */
void InOderTraverse(TreeNode *node) {
    if (node) {
        InOderTraverse(node->left);
        // printf("[%d,%s]", node->data.id, node->data.name);
        printf("%-3s", node->data.name);
        InOderTraverse(node->right);
    }
}

/**
 * 后序遍历: 左-右-根(左下-右侧左下向上)
 * @param node
 */
void PostOrderTraverse(TreeNode *node) {
    if (node) {

        PostOrderTraverse(node->left);
        PostOrderTraverse(node->right);
        // printf("[%d,%s]", node->data.id, node->data.name);
        printf("%-3s", node->data.name);
    }
}